package com.javabasic.algorithm.leetcode;

import org.junit.Test;

/**
 * @Author xiongmin
 * @Description //TODO
 * @Date 2020/1/15 17:02
 * @Version 1.0
 **/
public class PrimeNumberOfSetBitsInBinaryRepresentation {

    final int CAP = 1000000+4;
    int[] prime = new int[CAP];

    @Test
    public void main() {
        countPrimeSetBits(842,888);
    }

    private void init() {
        prime[0] = prime[1] = 1;
        for (int i = 2; i * i < CAP; i++) {
            if (prime[i] == 0) {
                for (int j = i*i; j < CAP; j+=i) {
                    prime[j] = 1;
                }
            }
        }
    }

    public int countPrimeSetBits(int L, int R) {
        int result = 0;
        init();
        for (int i = L; i <= R; i++) {
            int num = getNumOfOne(Integer.toBinaryString(i));
            if (prime[num] == 0) {
                result++;
                System.out.println(num + " "  + i);
            }
        }
        return result;
    }

    private int getNumOfOne(String str) {
        int len = str.length();
        int result = 0;
        for (int i = 0; i < len; i++) {
            if (str.charAt(i) == '1') {
                result++;
            }
        }
        return result;

    }
}
